package com;

import lombok.Data;

import java.util.concurrent.ConcurrentHashMap;

/**
 * @Author：ks
 * @Date：2022/9/17/0017 21:54
 * @Versiion：1.0
 * @Des: 实现LRU缓存：Lease Recently use
 */
public class LruCache {

    /**
     * 当前缓存的容量：淘汰策略是要根据容量来进行淘汰的
     */
    private int capacity;
    /**
     * hash
     */
    private ConcurrentHashMap<String,Node> hash;
    /**
     * 链表头、链表尾
     * 这两个节点一直都不变 真正意义上的头节点是第二个节点  真正意义上尾节点是倒数第二个
     */
    private Node head,tail;

    public LruCache(int capacity) {
        this.capacity = capacity;
        this.hash = new ConcurrentHashMap<>();
        this.head = new Node();
        this.head.pre = null;

        this.tail = new Node();
        this.tail.next = null;

        this.head.next = this.tail;
        this.tail.pre = this.head;
    }

    /**
     * 存数据节点
     * @param key
     * @param value
     */
    public void put(String key,Object value){
        if (!hash.containsKey(key)) {
            //不存在再 判断当前容量
            if(capacity <= hash.size()){
                //清除一个数据：LRU会将最近最少使用的数据放链表尾部 这样删除只需要删除尾部的节点
                Node tailNode = tail.pre;
                removeNode(tailNode);
                hash.remove(tailNode.key,tailNode);
            }
            Node node = new Node(key,value);
            hash.put(key, node);
            addToHead(node);
        }else{
            //已经存在的节点
            Node oldNode = hash.get(key);
            oldNode.setValue(value);
            //将当前节点移动链表头中
            moveToHead(oldNode);
        }
    }

    /**
     * 获取key
     * @param key
     * @return
     */
    public Object get(String key){
        Node node = null;
        if (hash.containsKey(key)) {
            //存在就移动一下位置
            node = hash.get(key);
            moveToHead(node);
        }
        return node;
    }

    /****************************内部方法********************************/

    /**
     * 移除节点
     * @param delNode
     */
    private void removeNode(Node delNode){
        Node preNode = delNode.pre;
        Node nextNode = delNode.next;
        preNode.next = nextNode;
        nextNode.pre = preNode;
    }

    /**
     * 节点移动至链表头
     * @param node
     */
    private void moveToHead(Node node){
        removeNode(node);
        addToHead(node);
    }

    /**
     * 节点移动至链表头
     * @param node
     */
    private void addToHead(Node node){
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }


    /***************************内部数据结构*******************************/
    @Data
    private class Node{
        private String key;
        private Object value;
        private Node pre;
        private Node next;

        public Node() {
            this.next = null;
            this.pre = null;
        }

        public Node(String key, Object value) {
            this.key = key;
            this.value = value;
            this.next = null;
            this.pre = null;
        }
    }
}
